package Test;

import java.util.PriorityQueue;
import java.util.Random;

/**
 * 快排
 */
public class 数组的第K大 {

    public static void main(String[] args) {
        int[] a={1,3,5,4,2};
        int n=5;
        int K=1;
        System.out.println(findKthLargest(a,2));

    }
    public static int findKth(int[] a, int n, int k){
        int target=n-k;
        int left=0;
        int right=n-1;
        while (true){
            int index=getindex(a,left,right);
            if(target>index) left=index+1;
            if(target<index) right=index-1;
            else if(target==index) return a[index];
        }
    }

   static int getindex(int[] a,int left,int right){
        Random random=new Random();
        int index = random.nextInt(right-left+1)+left;
        int compare=a[index];
        int t=a[left];
        a[left]=compare;
        a[index]=t;
        while (left<right){
            while (left<right&&a[right]>=compare){
                right--;
            }
            a[left]=a[right];
            while (left<right&&a[left]<=compare){
                left++;
            }
            a[right]=a[left];
        }
        a[left]=compare;
        return left;
    }

        public static int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> q = new PriorityQueue<>((a, b)->a-b);
            for (int x : nums) {
                if (q.size() < k ||x>q.peek()){
                    q.add(x);
                    System.out.println(x+"进队");
                }

                if (q.size() > k) q.poll();
            }
            return q.peek();
        }



}
